#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 510, M = N * N * 2;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int p[N];
LL dis[N];
//vector<PII>ans1;
PII ans1[N];
int cnt;
LL ans;
int find(int x)
{
	if (x != p[x])p[x] = find(p[x]);
	return p[x];
}
void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
struct node
{
	int a, b;
	LL w;
}S[M];
LL cmp(node a, node b)
{
	return a.w < b.w;
}
void kruskal()
{
	for (int i = 1; i <= n; i++)p[i] = i;
	for (int i = 1; i <= m; i++) {
		int a = S[i].a;
		int b = S[i].b;
		int a1 = find(a);
		int b1 = find(b);
		if (a1 != b1) {
			//ans1.push_back({ S[i].a,S[i].b });
			//ans += S[i].w;
			ans1[++cnt] = { a,b };
			p[a] = b;
			add(a, b, S[i].w);
			add(b, a, S[i].w);
			if (cnt == n - 1)break;
		}
	}
}
void dfs(int u, int fa)
{
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j != fa) {
			dis[j] = dis[u] + w[i];
			dfs(j, u);
		}
	}
}
int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof(h));
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		S[i] = { a,b,c };
	}
	sort(S + 1, S + m + 1, cmp);
	kruskal();
	dfs(1, -1);
	int t = 1;
	for (int i = 1; i <= n; i++) {
		if (dis[t] < dis[i]) {
			t = i;
		}
	}
	dfs(t, -1);
	for (int i = 1; i <= n; i++) {
		if (dis[t] < dis[i]) {
			t = i;
		}
	}
	cout << dis[t] / 2 << endl;
	//cout << ans << endl;
	/*for (auto x : ans1) {
		cout << x.first << " " << x.second << endl;
	}*/
	for (int i = 1; i <= cnt; i++) {
		cout << ans1[i].first << " " << ans1[i].second << endl;
	}
	return 0;
}